package q63_uniquePathsWithObstacles;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        // int[][] grid = {{0,0,0},{0,1,0},{0,0,0}};
        int[][] grid = {{0,1},{0,0}};
        System.out.println(s.uniquePathsWithObstacles(grid));
    }

    /**
     * 与前一题相似，但是存在障碍物的状况下，我们需要思考几个问题：
     * 1 某一个的方法数是否还是左格和上格的和？答案是肯定的，只需要把障碍物对应格子设置为0就可以了
     * 2 能否降低内存使用？在题目给了一个二维数组的情况下，我们可以直接复用，也就是把每一个格子的方法改为负数就可以了
     *   最后只需要将答案取负数即可
     * 3 唯一要考虑的是起点就是1，那么返回就是0
     * @param obstacleGrid
     * @return
     */
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {

        if (obstacleGrid[0][0] == 1) {
            return 0;
        }

        // 先设置第一行和第一列，如果遇到了1，那么就将该格子和之后的格子全部设置为0
        // （因为我们在复用给的数组，因此有可能遇到只有一行或者只有一列，而后面还有障碍，比如终点也是1）
        // 所以一定要遍历完第一行或者第一列
        for (int i = 0; i < obstacleGrid.length; i++) {
            if (obstacleGrid[i][0] == 1) {
                for (int j = i; j < obstacleGrid.length; j++) {
                    obstacleGrid[j][0] = 0;
                }
                break;
            }
            obstacleGrid[i][0] = -1;
        }

        for (int j = 0; j < obstacleGrid[0].length; j++) {
            if (obstacleGrid[0][j] == 1) {
                for (int i = j; i < obstacleGrid[0].length; i++) {
                    obstacleGrid[0][i] = 0;
                }
                break;
            }
            obstacleGrid[0][j] = -1;
        }

        // 然后只需要一个个遍历即可，遇到障碍置0
        // （因为比起其他上格或者左格是障碍的格子，我们一定会先遍历到障碍格子，所以不用考虑一个格子上或者左未置0的情况）
        for (int i = 1; i < obstacleGrid.length; i++) {
            for (int j = 1; j < obstacleGrid[0].length; j++) {
                obstacleGrid[i][j] = obstacleGrid[i][j] != 1 ? obstacleGrid[i - 1][j] + obstacleGrid[i][j - 1] : 0;
            }
        }

        return -obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1];
    }
}
